#include <stdio.h>

#define MAX_VEX_NUM 100
#define MAX_INT 0xffffffff

typedef struct {
    int vex_num;
    int adj_mat[MAX_VEX_NUM][MAX_VEX_NUM];
}Graph;

typedef struct {
    int vex_1;
    int vex_2;
    int weight;
}MSTEdge;

struct {
    int vex_adj;
    unsigned int lowcost;
}closedge[MAX_VEX_NUM];

void GetGraph(Graph *g);
void Prim(Graph *g, unsigned int u);

int main()
{
    Graph g;
    unsigned int u;

    GetGraph(&g);
    scanf("%d", &u);
    Prim(&g, u);

    return 0;
}

void GetGraph(Graph *g)
{
    int i, j;
    scanf("%d", &g->vex_num);
    for (i = 0; i < g->vex_num; i++) {
        for (j = 0; j < g->vex_num; j++) {
            scanf("%d", &g->adj_mat[i][j]);
        }
    }
    return;
}

int min(Graph *g)
{
    int i, k;
    unsigned int min;

    min = MAX_INT;
    for (i = 0; i < g->vex_num; i++) {
        if (closedge[i].lowcost != 0 && closedge[i].lowcost < min) {
            min = closedge[i].lowcost;
            k = i;
        }   
    }

    return k;
}

void Prim(Graph *g, unsigned int u)
{
    int i, j, k;

    for (i = 0; i < g->vex_num; i++) {
        if (g->adj_mat[u][i] != 0) {
            closedge[i].vex_adj = u;
            closedge[i].lowcost = g->adj_mat[u][i];
        } else {
            closedge[i].lowcost = MAX_INT;
        }
    }

    closedge[u].lowcost = 0;

    for (i = 1; i < g->vex_num; i++) {
        k = min(g);
        printf("%d %d %d\n", closedge[k].vex_adj, k, g->adj_mat[closedge[k].vex_adj][k]);
        closedge[k].lowcost = 0;
        for (j = 0; j < g->vex_num; j++) {
            if (g->adj_mat[k][j] != 0 && g->adj_mat[k][j] < closedge[j].lowcost) {
                closedge[j].lowcost = g->adj_mat[k][j];
                closedge[j].vex_adj = k;
            }
        }
    }

    return;
} 

/*
0  19  0  0  14  0   18
19   0    5   7   12   0   0
 0  5     0   3    0   0   0
 0  7   3     0    8    21  0
14  12  0  8     0    0   16
 0   0  0  21  0    0    27
18   0  0  0  16  27     0

*/